/*
 * Ej1.cpp
 * 
 * Copyright 2014 julian
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 * MA 02110-1301, USA.
 * 
 * 
 */
#include <iostream>
#include "Ej1.h"
#include <vector>
#include <utility>

using namespace std;

Ej1::Ej1(){}
/* Parámetros:
 * 
 * entrada: Vector de enteros con n + 2 valores.
 * 		 donde n es la cantidad de tablones y las dos posiciones extra representan a la tierra firme de cada lado del puente.
 * 
 * saltoMax: maxima cantidad de tablones que puede saltar
 * 
 */
pair <vector<unsigned short>,bool> Ej1::ejecutar(vector<unsigned short> entrada,unsigned int saltoMax){
	unsigned int posAEvaluar = 1; 
	unsigned int posCandidata = 0;
	unsigned int ultimaPosicion = 0;
		
	vector<unsigned short> salida;	
	bool tieneSol=true;
	
	//Si la entrada tiene solo dos valores entonces no tiene tablones
	if(entrada.size()==2) return make_pair(salida,false);
	
	
	vector<unsigned short>::iterator iterTablones = entrada.begin();
	//Empiezo a evaluar desde el primer tablon, la posición 0 y la final son tierra firme
	iterTablones++;
	
	//Recorro todos los tablones hasta llegar al otro lado
	for (vector<unsigned short>::iterator tablon = iterTablones; tablon != entrada.end(); ++tablon){
		//Si no está roto es candidato
		if(*tablon == 0 )
			posCandidata = posAEvaluar;
			
		posAEvaluar++;
		//Si supera la candtidad máxima de saltos me quedo con el salto mas lárgo posible
		if(posAEvaluar-ultimaPosicion > saltoMax || posAEvaluar == entrada.size()){
				//Sin solucion
				if(posCandidata-ultimaPosicion > saltoMax){
					tieneSol = false;
					break;					
				}
			
			
			ultimaPosicion=posCandidata;
			salida.push_back(ultimaPosicion);
		}
	
	}
	
	return make_pair(salida,tieneSol);
	
	
}
	
